class Solution {
public:
    int minCut(string s) {
        vector<vector<int> > dp(s.size(),vector<int>(s.size(),0));
        for(int i = s.size() - 1;i >= 0;i--){
            for(int j = i;j < s.size();j++){
                if(s[i] == s[j]){
                    if(j - i <= 2){
                        dp[i][j] = 1; 
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
            }
        }
        vector<int> ret(s.size(),INT_MAX);
        for(int i = 0;i < ret.size();i++){
            if(dp[0][i]){
                ret[i] = 0;
            }else{
                for(int j = 0;j < i;j++){
                    if(dp[j+1][i]){
                        ret[i] = min(ret[i],ret[j]+1);
                    }
                }
            }
        }
        return ret[s.size()-1];
    }
};
